吴师兄学算法

# LeetCode 322、零钱兑换

# 一、题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

# 二、题目解析

# 三、参考代码

# 1、Java 代码

class Solution {
    public int coinChange(int[] coins, int amount) {

        // 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况
        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
        // dp[0] 表示想要凑齐 0 元需要的最少硬币个数
        // dp[1] 表示想要凑齐 1 元需要的最少硬币个数
        // dp[14] 表示想要凑齐 14 元需要的最少硬币个数
        int[] dp = new int[amount + 1];

        // 首先将数组 dp 里面的值都初始化为 -1
        // -1 表示当前的金额还没有找到需要的最少硬币个数
        Arrays.fill(dp, -1);

        // 想要凑齐 0 元的最少硬币个数是 0 个
        dp[0] = 0;

        // 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少
        for(int i = 1 ; i <= amount ; i++){

            // 对于每个金额 i 来说，coins 中的每个面值小于 i 的硬币都可以尝试去拼凑 i
            // 比如 i = 8 ，coins 为 [1,2,5,7,10]
            // 其中 1，2，5，7 都小于 8
            // 1 可以尝试去拼凑 8
            // 2 可以尝试去拼凑 8
            // 5 可以尝试去拼凑 8
            // 7 可以尝试去拼凑 8
            // 所以，设置一个变量 j ，遍历数组 coins
            for(int j = 0 ; j < coins.length;j++){
                
                // 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i
                // 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额
                // 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数
                // 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果
                if(coins[j] <= i && dp[i-coins[j]] != -1){
                    // 这个时候，对于金额 i 来说
                    // 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数
                    // 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小
                    // 那么更新 dp[i]
                    if(dp[i] == -1 || dp[i-coins[j]] + 1 < dp[i]){
                        // 更新 dp[i]
                        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
                        // 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币
                        // 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币
                        dp[i] = dp[i - coins[j]] + 1;
                    }

                }
            }
        }
        
        // dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数
        // 返回这个结果就行
        return dp[amount];
    }
}

# **2、**C++ 代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况
        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
        // dp[0] 表示想要凑齐 0 元需要的最少硬币个数
        // dp[1] 表示想要凑齐 1 元需要的最少硬币个数
        // dp[14] 表示想要凑齐 14 元需要的最少硬币个数
        // 首先将数组 dp 里面的值都初始化为 -1
        // -1 表示当前的金额还没有找到需要的最少硬币个数
        vector<int> dp( amount + 1 , -1 );

        // 想要凑齐 0 元的最少硬币个数是 0 个
        dp[0] = 0;

        // 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少
        for(int i = 1 ; i <= amount ; i++){

            // 对于每个金额 i 来说，coins 中的每个面值小于 i 的硬币都可以尝试去拼凑 i
            // 比如 i = 8 ，coins 为 [1,2,5,7,10]
            // 其中 1，2，5，7 都小于 8
            // 1 可以尝试去拼凑 8
            // 2 可以尝试去拼凑 8
            // 5 可以尝试去拼凑 8
            // 7 可以尝试去拼凑 8
            // 所以，设置一个变量 j ，遍历数组 coins
            for(int j = 0 ; j < coins.size();j++){
                
                // 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i
                // 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额
                // 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数
                // 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果
                if(coins[j] <= i && dp[i-coins[j]] != -1){
                    // 这个时候，对于金额 i 来说
                    // 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数
                    // 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小
                    // 那么更新 dp[i]
                    if(dp[i] == -1 || dp[i-coins[j]] + 1 < dp[i]){
                        // 更新 dp[i]
                        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
                        // 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币
                        // 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币
                        dp[i] = dp[i - coins[j]] + 1;
                    }

                }
            }
        }
        
        // dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数
        // 返回这个结果就行
        return dp[amount];
    }
};

# 3、Python 代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况
        # dp[i] 表示想要凑齐 i 元需要的最少硬币个数
        # dp[0] 表示想要凑齐 0 元需要的最少硬币个数
        # dp[1] 表示想要凑齐 1 元需要的最少硬币个数
        # dp[14] 表示想要凑齐 14 元需要的最少硬币个数
        # 首先将数组 dp 里面的值都初始化为 -1
        # -1 表示当前的金额还没有找到需要的最少硬币个数
        dp = [ -1 for _ in range( amount + 1 )]

        # 想要凑齐 0 元的最少硬币个数是 0 个
        dp[0] = 0

        # 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少
        for i in range ( 1 , amount + 1 ) :

            # 对于每个金额 i 来说，coins 中的每个面值小于 i 的硬币都可以尝试去拼凑 i
            # 比如 i = 8 ，coins 为 [1,2,5,7,10]
            # 其中 1，2，5，7 都小于 8
            # 1 可以尝试去拼凑 8
            # 2 可以尝试去拼凑 8
            # 5 可以尝试去拼凑 8
            # 7 可以尝试去拼凑 8
            # 所以，设置一个变量 j ，遍历数组 coins
            for j in range( 0 , len(coins) ): 
                
                # 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i
                # 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额
                # 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数
                # 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果
                if coins[j] <= i and  dp[i-coins[j]] != -1  :
                    # 这个时候，对于金额 i 来说
                    # 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数
                    # 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小
                    # 那么更新 dp[i]
                    if dp[i] == -1 or dp[i-coins[j]] + 1 < dp[i] : 
                        # 更新 dp[i]
                        # dp[i] 表示想要凑齐 i 元需要的最少硬币个数
                        # 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币
                        # 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币
                        dp[i] = dp[i - coins[j]] + 1

        # dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数
        # 返回这个结果就行
        return dp[amount]

← LeetCode 72、编辑距离 →